In many application environments, an image is encoded (or compressed) to reduce the total amount of data needed to represent the image. The compressed data may then be stored or transmitted more efficiently than the original uncompressed image data.
Block truncation coding (BTC) is a common image encoding technique. BTC is a simple and fast compression method and therefore is useful in printing applications. The BTC technique quantizes blocks of pixels in an image in a way that preserves the first and second moments of pixel values in the block (i.e., the mean of values and the mean of squares of values in the quantized blocks are the same as in the original blocks). In accordance with the BTC technique, a grayscale image is divided into square blocks of m pixels. The pixels of a given block with values smaller than the mean pixel value for the given block are segmented into a light pixel group and the pixels with values greater than or equal to the mean pixel value are segmented into a dark pixel group. Two quantization levels a, b are computed for the given pixel as follows:a=x −σ√{square root over (q /(m−q))}   (1)b=x +σ√{square root over ((m−q)/q )}   (2)where x is the mean of the pixel values in the block, σ is the standard deviation of the pixel values in the block, and q is the number of pixels in the light pixel group. The pixel values in the light pixel group are mapped to a, and the pixel values in the dark pixel group are mapped to b. Each block is encoded as (x, σ, B), where B is a binary vector of length m referred to as a mask (also called a bit plane or a bit map). The mask B indicates which pixel locations in a block are assigned to the light pixel group and which pixel locations are assigned to the dark pixel group. During decoding, the quantization levels a and b are computed from the values x and σ in the encoded data using equations (1) and (2), and every pixel in the decoded image is assigned one of the quantization levels in accordance with the mask B.
By representing each block of pixels by first and second moment values and a mask, the BTC method achieves a significant compression of the original image data. Additional compression of the image data may be achieved by encoding the BTC quantization data using, for example, run-length coding and variable length coding techniques.